package com.platform.modules.alg.alglib.hdu4006;

import java.util.PriorityQueue;

public class Hdu4006 {
    public String output = "";

    public String cal(String input) {
        int i, n, k, num;
        char c;

        String[] line = input.split("\n");

        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        k = Integer.parseInt(words[1]);

        PriorityQueue<Integer> q = new PriorityQueue<>(); // 默认为小顶堆

        for (i = 1; i <= n; i++) {
            String[] command = line[i].split(" ");
            c = command[0].charAt(0);
            if (c == 'I') {
                num = Integer.parseInt(command[1]);
                if (q.size() < k) // 堆中元素个数小于 k
                    q.add(num);
                else if (q.peek() < num) { // 当堆顶小于输入元素时
                    q.poll();
                    q.add(num); // 堆顶出队，元素入队
                }
            } else //堆中永远保存最大的k个元素
                output += q.peek() + "\n";//堆顶即为第k大元素
        }
        return output;
    }
}
